1. Field of the Invention
The present invention relates to the design of communication pathways within digital systems. More specifically, the present invention relates to a method and an apparatus for performing error-detection and/or error-correction on data packets transmitted across multiple data lines within a digital system.
2. Related Art
As computer systems become increasingly faster, data must be transmitted between computer system components at increasingly faster rates. These faster transmission rates increase the likelihood of communication errors. These communication errors may cause a particular data bit to flip its value, or they may cause a bit to always transmit a zero or one regardless of its intended value. The goal of error-detection and error-correcting systems is to detect and recover from such communication errors.
In a multi-hop communication network, error-detection/correction can be done at the receiver of the data and/or along the communication media at each hop. Traditional error-detection/correction in communication systems is done in space: the entire data word, from bit 0 to bit n (where n can be, for example, 8, 16, 32, or 64 bytes), is examined and error-checked/corrected all at once. This check is repeated for each word in the sequence of words that make up a packet of data. For example, a data packet may include 64 such words, and each of these 64 words is processed individually.
These traditional methods of error-detection and correcting are not without their drawbacks. An error-correcting operation typically requires time proportional to log2 n to examine a full n-bit data word. For example, performing a parity check over 64 bits requires six levels of two-input XOR gates. In addition, the width of the network has to be expanded to handle the additional bits required for error detection. In a typical system with 64-bit words and standard Error Correction Codes (ECC), the network must be expanded by eight bits to handle the ECC information.
In addition to the increased network requirements, traditional systems require the whole word to be received before error-correction analysis can begin. Because of the complexity and the time delay that results, several packets can pass through a station before it is determined that one of the words was corrupt.
Hence, what is needed is a method and an apparatus for performing error-detection and error-correction on a communication network without the problems listed above.